#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct tree
{
int data;
struct tree *left;
struct tree *right;
}*root,*temp;
struct tree* crtree(void);
void preorder(struct tree *);
struct tree * del(int);
void main()
{
clrscr();
root=temp=NULL;
printf("\n press any key to create tree");
getch();
root=crtree();
preorder(root);
printf("\n enter item u want to delete");
int cm;
scanf("%d",&cm);
root=del(cm);
preorder(root);
getch();

getch();
}

struct tree* crtree(void)
{
 clrscr();
 struct tree *root;
 root=NULL;
 int no,dir,pr,n;
 char ch;
 struct tree *parent;
 dir=0;
 pr=0;
 printf("\n  creating tree....\n\n");
 printf("\n please enter the root\n");
 scanf("%d",&n);
 temp=(struct tree*)malloc(sizeof(struct tree));
 temp->data=n;
 temp->right=temp->left=NULL;
 if(root==NULL)
 root=temp;
 printf("\n press y to enter more elements and n to quit\n");
ch= getch();
 while(ch=='y' || ch=='Y')
 {
  printf("\n enter the value of node");
  scanf("%d", &n);
  struct tree *x;
  x=root;
  parent=root;
  if(n==root->data)
  {printf("\nalready entered\n");
   pr=1;
   continue;

   }
   else
   {
    while(x!=NULL)
    {
      if(n<x->data)
      {
      parent=x;
      x=x->left;
      dir=1;
      }
      else if(n>x->data)
      {
      parent=x;
      x=x->right;
      dir=2;
      }
      else
      {
      printf("\n already entered \n");
      printf(" \n enter y to continue and n to quit");
      ch=getch();
      break;
      }
      }
      if(!pr)
      {
       temp=(struct tree*)malloc(sizeof(struct tree));
 temp->data=n;
 temp->right=temp->left=NULL;
 if(dir==1)
 parent->left=temp;
 else
  parent->right=temp;
 printf("\n press y to enter more elements and n to quit\n");
 ch=getch();
  }
}

}
return root;
}

void preorder(struct tree *p)
{
if(p!=NULL)
{
printf("%d->",p->data);
preorder(p->left);
preorder(p->right);
}
}

struct tree * del(int n)
{
struct tree * x,*parent,*p,*subparent,*delleft;
x=root;
int fnd,dir;
dir=0;
fnd=0;
parent=root;
while(x!=NULL)
{
if(n==x->data)
{
fnd=1;
break;
}
else if(n>x->data)
{
parent=x;
x=x->right;
dir=2;
fnd=0;
}
else if(n<x->data)
{
parent=x;
x=x->left;
fnd=0;
dir=1;
}
}

if(fnd==1)
{
delleft=x->left;

if(x->left==NULL && x->right==NULL)
{
  if(dir==1)
  {
  parent->left=NULL;
  return root;
  }
  else if(dir==2)
  {
  parent->right=NULL;
  return root;
  }
  }
 else if(x->left==NULL || x->right==NULL)
 {
 struct tree *chld;
 if(x->left!=NULL)
 {
 chld=x->left;
 }
 else
 chld=x->right;
 if(dir==1)
 {
 parent->left=chld;
 return root;
 }
 else if  (dir==2)
 {
 parent->right=chld;
 return root;
 }
}
else if (x->left!=NULL && x->right!=NULL)
{
struct tree *subchld,*subparent,*g,*z;
g=x->right;
if(g->left==NULL)
{
if(dir==1)
{
parent->left=g;
g->left=delleft;
return root;
}
else if(dir==2)
{
parent->right=g;
g->left=delleft;
return root;
}
}
else
{
subparent=g;
while(g->left!=NULL)
{
 subparent=g;
 g=g->left;
 }
z=g->right;
subparent->left=z;
x->data=g->data;
return root;

}
}
}
else
{
printf("\n item not found \n");
}

return root;
}

